/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/15
 */
// 1ms
public class _18_51_NQueens2 {
    private int n;
    public int count;
    public int eraseHigh1;
    private int[] colsCache;
    List<List<String>> res = new ArrayList<>();

    // 撇 i + j，捺 i - j + n
    public List<List<String>> solveNQueens(int n) {
        if (n < 1) return new ArrayList<>();
        this.n = n;
        eraseHigh1 = (1 << n) - 1;
        colsCache = new int[n];
        for (int i = 0; i < colsCache.length; i++)
            colsCache[i] = -1;
        dfs(0, 0, 0, 0);
        return res;
    }

    private void dfs(int row, int cols, int pie, int na) {
        if (row >= n) {
            ++count;
            addToResult(res);
            return;
        }
        int bits = (~(cols | pie | na)) & eraseHigh1;
        while (bits > 0) {
            int p = bits & -bits;
            int col = 0;
            int tempP = p;
            while (tempP != 0) {
                col++;
                tempP >>= 1;
            }
            colsCache[n - col] = row;
            dfs(row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
            colsCache[n - col] = -1;
            bits &= bits - 1;
        }
    }

    private void addToResult(List<List<String>> result) {
        List<String> newSolution = new ArrayList<>();
        char[] temp = new char[n];
        for (int col = 0; col < n; col++) {
            int key = colsCache[col];
            for (int row = 0; row < n; row++)
                temp[row] = '.';
            temp[key] = 'Q';
            newSolution.add(new String(temp));
        }
        result.add(newSolution);
    }

    public static void myPrint(List<List<String>> result) {
        for (List<String> list : result) {
            for (String s : list) {
                System.out.println(s.replace('.', '+'));
            }
            System.out.println("-------------");
        }
    }

    public static void main(String[] args) {
        _18_51_NQueens2 nQueens = new _18_51_NQueens2();
        myPrint(nQueens.solveNQueens(4));
        System.out.println(nQueens.count);
    }
}
